% ---------------------------------------------------------------------------
% Author guideline and sample document for EG publication using LaTeX2e input
% D.Fellner, v1.13, Jul 31, 2008

\documentclass{egpubl}
\usepackage{eg2010}

% --- for  Annual CONFERENCE
\ConferenceSubmission   % uncomment for Conference submission
% \ConferencePaper        % uncomment for (final) Conference Paper
% \STAR                   % uncomment for STAR contribution
% \Tutorial               % uncomment for Tutorial contribution
% \ShortPresentation      % uncomment for (final) Short Conference Presentation
% \Areas                  % uncomment for Areas contribution
% \MedicalPrize           % uncomment for Medical Prize contribution
% \Education              % uncomment for Education contribution
%
% --- for  CGF Journal
% \JournalSubmission    % uncomment for submission to Computer Graphics Forum
% \JournalPaper         % uncomment for final version of Journal Paper
%
% --- for  CGF Journal: special issue
% \SpecialIssueSubmission    % uncomment for submission to Computer Graphics Forum, special issue
% \SpecialIssuePaper         % uncomment for final version of Journal Paper, special issue
%
% --- for  EG Workshop Proceedings
% \WsSubmission    % uncomment for submission to EG Workshop
% \WsPaper         % uncomment for final version of EG Workshop contribution
%
 \electronicVersion % can be used both for the printed and electronic version

% !! *please* don't change anything above
% !! unless you REALLY know what you are doing
% ------------------------------------------------------------------------

% for including postscript figures
% mind: package option 'draft' will replace PS figure by a filname within a frame
\ifpdf \usepackage[pdftex]{graphicx} \pdfcompresslevel=9
\else \usepackage[dvips]{graphicx} \fi

\PrintedOrElectronic

% prepare for electronic version of your document
\usepackage{t1enc,dfadobe}

\usepackage{egweblnk}
\usepackage{cite}

\usepackage{subfigure}
\usepackage{tikz}
\usepackage{pgf}
\usepackage{xcolor}
\usetikzlibrary{fadings}
\usepackage{overpic}
\usepackage[ruled,vlined]{algorithm2e}
\usepackage{mathrsfs}

% For backwards compatibility to old LaTeX type font selection.
% Uncomment if your document adheres to LaTeX2e recommendations.
% \let\rm=\rmfamily    \let\sf=\sffamily    \let\tt=\ttfamily
% \let\it=\itshape     \let\sl=\slshape     \let\sc=\scshape
% \let\bf=\bfseries

% end of prologue

%\input{EGauthorGuidelines-body.inc} % ---------------------------------------------------------------------
% EG author guidelines plus sample file for EG publication using LaTeX2e input
% D.Fellner, v1.16, Jan 21, 2009


\title[]%
      {Tree Modeling Based on Inverse L-system from Two Images}

% for anonymous conference submission please enter your SUBMISSION ID
% instead of the author's name (and leave the affiliation blank) !!
%\author[]
%       {R.\,X. Sun, H.\,Y. Li
%        and J.\,Y. Jia
%%        S. Spencer$^2$\thanks{Chairman Siggraph Publications Board}
%        \\
%% For Computer Graphics Forum: Please use the abbreviation of your first name.
%         Research Center of Graphics and Image, School of Software Engineering, Tongji University, China
%%        $^2$ Another Department to illustrate the use in papers from authors
%%             with different affiliations
%       }
\author[]
       {ID: paper1094
       \\
       }

% ------------------------------------------------------------------------

% if the Editors-in-Chief have given you the data, you may uncomment
% the following five lines and insert it here
%
% \volume{27}   % the volume in which the issue will be published;
% \issue{1}     % the issue number of the publication
% \pStartPage{1}      % set starting page


%-------------------------------------------------------------------------
\begin{document}

\maketitle

\begin{abstract}
This paper proposes an approach to model trees
using inverse L-system extracted from two images.
This approach is different from the traditional way
of constructing L-systems that normally requires
manually adjustment and expertise in botany.
In this approach, 3D skeleton of the visible trunk
is first recovered from two images using vision method.
A parametric L-system is then extracted from the
recovered 3D skeleton.
The extracted L-system is complemented by
computing the parameters for generating
the occluded branches and the leaves
under the constraint of silhouettes in the images.
%The occluded trunk and the leaves are generated
%by the extracted L-system under the constraint
%of silhouettes in the images.
The extracted L-system can faithfully preserve the
overall shape of the tree and be used to generate
realistic 3D tree model.
Moreover, being a light-weighted rule-based model,
L-system is more preferable than mesh model
to transfer on Web, which may bring great benefit
to Web virtual reality applications.

\begin{classification} % according to http://www.acm.org/class/1998/
\CCScat{Computer Graphics}{I.3.7}{Three-Dimensional Graphics and Realism }{Virtual reality}
\end{classification}

\end{abstract}





%-------------------------------------------------------------------------
\section{Introduction}

Nowadays virtual reality techniques are widely used in Web
applications, esp. virtual tour, virtual natural landscape
and virtual agriculture. It is well known that tree is a
key component in the natural environment, thus
modeling trees plays an important role in these fields. For now, more
light-weighted and intelligent tree modeling methods are demanded
urgently. In aims of light-weighted modeling, highly parametric models
are needed. On the other hand, vision methods are employed
to model trees from images for more intelligence and realistic.

The techniques for modeling trees can be roughly classified as
rule-based and image-based. Rule-based techniques use a set of
generative rules or grammar to create branches and leaves
iteratively. The representative of this class is L-system introduced
in~\cite{Lindenmayer68} for describing fractal objects. Now L-system
has been carefully studied and extended to different versions, e.g. the
parametric L-system~\cite{Prusinkiewicz90} and the differential
L-system~\cite{Prusinkiewicz93}.
Recently a sketch-based approach to construct L-system
is proposed in~\cite{Anastacio08}.
Rule-based techniques supply strong
controls to the form of trees and are able to create light-weighted
tree models, but expertise in botany is normally required
to adjust the parameter values and the results
are often too mechanical to be close to natural trees.

Image-based techniques try to recover the tree geometries directly
using single or multiple photographs. Visual hull was reconstructed
from several images to aid the tree modeling in \cite{Reche04,
Shlyakhter01}. In addition, Quan proposed an
approach in \cite{Quan06} to recover plant geometry from
reconstructed point clouds.
This method was later extended in~\cite{Tan07} to model trees specifically.
Other image-based methods, e.g. particle flows~\cite{Neubert07},
single-image~\cite{Tan08} and sketch-based~\cite{Chen08}, are also
proposed.
Image-based techniques are highly
intelligent and able to assure high reality of the models because the
models are reconstructed from real images. Nevertheless, it is
inconvenient for users to change the tree models, and the result can
severely impede the transmission in the network due to the huge
amount of data.

To avoid the drawbacks of current techniques, a new approach is proposed
in this paper. This method combines rule-based and image-based
techniques and is able to intelligently model light-weighted trees.
In this approach, 3D skeleton of the visible trunk and the branching structure
are recovered from the two input images using binocular vision methods.
A parametric L-system is then extracted from the reconstructed 3D skeleton and
the branching structure.
The occluded trunk, tiny branches and leaves are generated by
the L-system under the constraint of the tree silhouettes in the images.
The extracted L-system is a highly parametric rule-based tree model
that preserves all the features of the tree shape.
It is light-weighted to transfer on Web and can be fully translated into
a mesh model for rendering.

In sum, the proposed approach can be divided into four steps, as illustrated in
Figure~\ref{fig:overview}. Each step is outlined as follows:

\begin{itemize}
\item \textbf{Branching structure recovery of visible trunk:}
Branching structure describes the parent-child context between the branches.
The visible part of the tree trunk and its 2D skeleton are first extracted from the source images.
The branching structure is then recovered from the 2D skeleton.
\item \textbf{3D reconstruction of visible skeleton:} Using binocular vision methods,
the 3D skeleton of the visible trunk is reconstructed.
\item \textbf{L-system extraction:} Through the analysis of the branching structure,
a parametric L-system is extracted from the reconstructed 3D skeleton.
Then the parameters of the L-system for generating
the occluded branches and the leaves are computed under the instruction of
the extracted L-system and the constraint of silhouettes in the images.
\item \textbf{Model usage:} The extracted L-system is used to generate
3D tree model for rendering.
It is also adjustable for other usages (e.g. tree growth simulation).
\end{itemize}

%-------------------------------------------------------------------------
\section{Branching structure recovery of visible trunk}
\label{sec:Pre-processing}

To recover the branching structure, the visible trunk of the tree
must be first extracted from the source images.
That is actually a bipartition
process. There exist a number of methods to complete this task, such
as $SWA$~\cite{nature/Sharon06}, and
Ncut~\cite{DBLP:journals/pami/ShiM00}. This study borrows the idea
of $SWA$ to segment the tree trunk. An example is shown in
Figure~\ref{fig:preprocessing}. Panels (a) and (b) are respectively
the source image and the corresponding tree trunk. For details of
the $SWA$ algorithm, please refer to~\cite{nature/Sharon06}.

After bipartition, a thinning algorithm is needed to obtain the
2D skeleton of the tree trunk. Skeleton is the best way to describe
the main character of a tree. It preserves the morphological
feature of a tree and is easy for processing. Our thinning approach is
based on the distance transform~\cite{Borgefors86}. The distance
transform of an image is defined as a new image in which every
output pixel is set to a value equal to the distance to the nearest
zero pixel in the input image. All points that have the maximum
distance in the gradient direction compose the skeleton of the
image, as shown in Figure~\ref{fig:preprocessing:c}. The
``Non-maximum suppression'' method \cite{Canny86} is applied on the
distance to filtering the non-skeleton points. The gradient
directions at crossing points are ambiguous so the skeleton
would break at crossing points, as shown in
Figure~\ref{fig:preprocessing:d}. As a result, the skeleton is
divided into several continuous areas, each of which corresponds to
a branch segment.

\begin{figure}[h]
  \centering
  \subfigure[]{
    \label{fig:preprocessing:a} %% label for first subfigure
    \includegraphics[scale=0.5]{Figure/Preprocessing(a).jpg}}
  \hfill
  \subfigure[]{
    \label{fig:preprocessing:b} %% label for second subfigure
    \includegraphics[scale=0.5]{Figure/Preprocessing(b).jpg}}
  \hfill
  \subfigure[]{
    \label{fig:preprocessing:c} %% label for first subfigure
    \includegraphics[scale=0.5]{Figure/Preprocessing(c).jpg}}
  \hfill
  \subfigure[]{
    \label{fig:preprocessing:d} %% label for second subfigure
    \includegraphics[scale=0.5]{Figure/Preprocessing(d).jpg}}
  \caption{(a) Source image; (b) Segmentation; (c) Distance transform; (d) Non-maximum suppression.}
  \label{fig:preprocessing} %% label for entire figure
\end{figure}

Once all branches are obtained, the remaining work is to find the
parent for each branch. To do this, two kinds of crossing points
have to be considered. One is the real branching point of
the tree and the other is the overlapping point of two
individual branches. The latter essentially contains the fake
branching relationship caused by visual errors.
Our strategy of finding the parent for a branch is realized through analyzing both the distance and angle between them.

A branch can be represented by a starting point $S$ and a
terminal point $T$. In a continuous skeleton, the way of
determining the starting point $S$ is to compute the spatial
distance from the current point to the tree root. The point with the
smaller distance is considered as $S$, the other is $T$. Now we use
an example to explain our strategy of handling overlapping points,
as shown in Figure~\ref{fig:branchingstructure}. For branch $b$
with the starting point $S_b$, a circle with radius $d$ is first
drawn at $S_b$. Branches with an end point falling in this
circle are considered as candidate parents of $b$. Therefore, $c_1$ and $c_2$ are candidate parents of $b$, however,
$b'$ is not. $b''$ cannot be selected as a candidate parent of $b$
because it is not connected to $b$.

The angle difference is the other significant factor considered in our strategy.
Assuming that the angle from a branch to its parent is the least, the process of searching the parent begins
from the inverse direction of the branch, proceeds on both sides of this direction, and stops until the first candidate appears.
This candidate parent will be considered as the final parent.
For instance, in
Figure~\ref{fig:branchingstructure}, $c_1$ is the first candidate parent appearing on both sides of the inverse direction of $S_bT_b$, so the
parent of $b$ is $c_1$. As such, $c_2$ is identified as the parent of branch $b'$.

After finding the parent, the starting point of each branch is set to the terminal point of the parent branch.
Thus the skeleton is also reconnected.

\begin{figure}
  \centering
  \begin{overpic}{Figure/binary.jpg}

\begin{tikzpicture}[path fading=south]

%help line
%\draw[help lines, gray] (-3,-3) grid (5,5);

%circle bkg
\fill[blue, very nearly transparent] (2,2) circle(2);

%angel bkg
\fill[rotate around={30 - 45:(2,2)}, gray, semitransparent, path fading, fading transform={rotate=-45}] (2,2) -- (2,-3) arc (-90:-150:5);

%circle
\draw[blue, dashed] (2,2) circle(2);

%radius
\draw[rotate around={90:(2,2)}, blue, dashed, ->] (2,2) -- node[above] {$d$} (2,0);

%rays
\draw[rotate around={-75:(2,2)}, black!80, dashed, ->] (2,2) to node[above] {$r_1$} (2,-3);
\draw[rotate around={-15:(2,2)}, black!80, dashed, ->] (2,2) to node[right] {$r_2$} (2,-3);
\draw[rotate around={-45:(2,2)}, black!80, dashed, ->] (2,2) to (2,-3);

%arcs
\draw[rotate around={-45:(2,2)}, black!80, dashed] (2,-0.5) arc (-90:-120:2.5);
\draw[rotate around={-45:(2,2)}, black!80, dashed] (2,-0.7) arc (-90:-60:2.7);
\node[black!80] (alpha1) at (0.1,0.8) {$\alpha$};
\node[black!80] (alpha2) at (0.8,-0.1) {$\alpha$};

%branch
\draw[line width=1] (2,2) to node[anchor=south east] {$b$} (4,4);
\node[anchor=south east] (sb) at (2,2) {$S_b$};
\node[anchor=south east] (tb) at (4,4) {$T_b$};
\fill (2,2) circle (2pt);
\fill (4,4) circle (2pt);

%branch'
\draw[black!80, line width=1] (1,2) to node[above] {$b'$} (-2,3);
\node[black!80, above] (sb') at (1,2) {$S'_{b}$};
\node[black!80, above] (tb') at (-2,3) {$T'_{b}$};
\fill[black!80] (1,2) circle (2pt);
\fill[black!80] (-2,3) circle (2pt);

%branch''
\draw[black!80, line width=1] (-2,0) to node[above] {$b''$} (0.5,1.25);
\node[black!80, above] (sb') at (-2,0) {$S''_{b}$};
\node[black!80, right] (tb') at (0.5,1.25) {$T''_{b}$};
\fill[black!80] (-2,0) circle (2pt);
\fill[black!80] (0.5,1.25) circle (2pt);

%c1
\draw[red, line width=1] (0,-2) to node[left] {$c_1$} (1.5,1);
\node[red, left] at (0,-2) {$S_1$};
\node[red, above] at (1.5,1) {$T_1$};
\fill[red] (0,-2) circle (2pt);
\fill[red] (1.5,1) circle (2pt);

%c2
\draw[green, line width=1] (4.5,-0.5) to node[above] {$c_2$} (2.5,1);
\node[green, above] at (4.5,-0.5) {$S_2$};
\node[green, above] at (2.5,1) {$T_2$};
\fill[green] (4.5,-0.5) circle (2pt);
\fill[green] (2.5,1) circle (2pt);

\end{tikzpicture}
\end{overpic}
\caption{Finding the parent for branch $b$. Gray thick lines are
branches in the segmented image. $b$, $b'$, $b''$, $c_1$ and $c_2$
are extracted skeletons. Finally $c_1$ is chosen as the
parent of $b$ due to the smaller distance and angle difference.}
  \label{fig:branchingstructure} %% label for entire figure
\end{figure}

%-------------------------------------------------------------------------
\section{3D reconstruction of visible skeleton}
\label{sec:reconstruction}

Using binocular vision methods, the coordinates of a 3D point
can be estimated from a pair of corresponding points in two images.
The essential problem in this step is finding corresponding branches
from two images.
Classical stereo matching methods extract feature points,
e.g. corner~\cite{Harris88}, edge~\cite{Canny86} and SIFT~\cite{Lowe04},
from both source images, then apply matching algorithm on them.
It is normally time-consuming and noise-sensitive of these methods.
Since our approach extracts the skeleton and recovers the branching structure,
it is able to take advantage of the topology structure for more accurate
and efficient matching.
We propose a new topology matching with feature assistance method
for branch correspondence.
This method scans the two branching structures recovered from both source images bottom-up.
Branching structure records the parent for each branch.
The branch who has no parent is the root branch.
The two root branches in both branching structure are matched initially.
For the branches already matched, their children are matched from left to right.
Repeat this process until all branches are matched or error occurs.
Due to the perspective change and the uncertainty during the image processing,
the two branching structures may have different structures
in some local areas, and that will cause matching errors.
Figure~\ref{fig:error} shows an example of matching error
caused by perspective change.
To handle these errors, our strategy uses SIFT~\cite{Lowe04} feature
and match propagation~\cite{Lhuillier05} for assistance.
Assuming that one of the two branching structures is true,
our method finds the corresponding points for the starting and the terminal
points of the mismatched branch in the other image.
The SIFT feature points in the error area are extracted and matched in both image,
then the correspondence is propagated until the corresponding
starting and terminal points of the mismatched branch are found.
Though the assumption of the true branching structure may be false,
e.g. Figure~\ref{fig:error:a}, it only change the starting point
of the mismatched branch, which does not affect the global shape
of the tree.

\begin{figure}
  \centering
  \subfigure[]{
    \label{fig:error:a} %% label for first subfigure
    \includegraphics[scale=0.5]{Figure/error_left_source.jpg}
    \includegraphics[scale=0.5]{Figure/error_left_bs.jpg}
    }
  \hfill
  \subfigure[]{
    \label{fig:error:b} %% label for first subfigure
    \includegraphics[scale=0.5]{Figure/error_right_source.jpg}
    \includegraphics[scale=0.5]{Figure/error_right_bs.jpg}
    }
  \caption{Matching error caused by perspective change.
  The blue branch is the mismatched one.}
  \label{fig:error} %% label for entire figure
\end{figure}

Since a branch is represented by a starting point and a terminal
point, 3D skeleton reconstruction is equivalent to estimating the 3D
positions of both points.
Branch correspondence means the starting and the terminal point
correspondence.
With these corresponding points, the method in~\cite{Hartley00}
is used to calculate the 3D coordinates of all the points.

%-------------------------------------------------------------------------
\section{L-system extraction}
\label{sec:lsystemextraction}

Two important components of L-system are productions and parameters.
The essence of production extraction is to extract the minimal
structures of the branching context. Parameters provide better
control of the tree shape and can be computed with the 3D skeletons
containing the information of the tree shape.

\subsection{Production extraction}
\newtheorem{dfn}{Statement}
Before extracting productions, we need to define two categories of
branches first: the branches with no children are \textbf{terminal},
the others are \textbf{internal}. Each internal branch is associated
with a unique ID. Terminal branches have a common ID $t$ because
they have the same structure. A production has the form of
``$predecessor \rightarrow successor$'', where predecessor
represents the ID of a parent branch and successor is a string
composed of IDs of children branches belonging to predecessor.
\begin{figure}[h]
  \centering
\begin{tikzpicture}
[grow'=up,
level 1/.style={level distance=48},
level 2/.style={level distance=32},
level 3/.style={level distance=32},
level 4/.style={level distance=32},
level 5/.style={sibling distance=10, level distance=32}]
\coordinate
child[red]{
    child[orange, sibling distance=10 * 7]{
        child[green, sibling distance=10 * 2]{
            child[blue, sibling distance=10 * 3]{
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                edge from parent
                node[left]{$8$}
            }
            child[blue, sibling distance=10 * 2]{
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                edge from parent
                node[right]{$9$}
            }
            edge from parent
            node[left]{$3$}
        }
        child[green, sibling distance=10 * 2.5]{
            child[blue, sibling distance=10 * 1]{
                %node{$t$}
                edge from parent[dashed]
            }
            child[blue, sibling distance=10 * 1]{
                %node{$t$}
                edge from parent[dashed]
            }
            edge from parent
            node[right]{$4$}
        }
        edge from parent
        node[left]{$1$}
    }
    child[orange, sibling distance=10 * 11]{
        child[green, sibling distance=10 * 5.5]{
            child[blue, sibling distance=10 * 2]{
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                edge from parent
                node[left]{$10$}
            }
            child[blue, sibling distance=10 * 2]{
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                edge from parent
                node[right]{$11$}
            }
            edge from parent
            node[below]{$5$}
        }
        child[green, sibling distance=10 * 0]{
            child[blue, sibling distance=10 * 2.5]{
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                edge from parent
                node[left]{$12$}
            }
            child[blue, sibling distance=10 * 0]{
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                edge from parent
                node[anchor=south east]{$13$}
            }
            child[blue, sibling distance=10 * 2.5]{
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                edge from parent
                node[right]{$14$}
            }
            edge from parent
            node[left]{$6$}
        }
        child[green, sibling distance=10 * 4]{
            child[blue, sibling distance=15 * 1]{
                %node{$t$}
                edge from parent[dashed]
            }
            child[blue, sibling distance=10 * 1]{
                %node{$t$}
                edge from parent[dashed]
            }
            edge from parent
            node[below]{$7$}
        }
        edge from parent
        node[above]{$2$}
    }
    edge from parent
    node[left]{$r$}
};
\end{tikzpicture}
\caption{The illustration of a branching structure. Dashed lines represent terminal branches,
others are internal branches. IDs of internal branches are marked
out and the ID $t$ of terminal branches is omitted here.}
\label{fig:skeleton} %% label for entire figure
\end{figure}

As shown in Figure~\ref{fig:skeleton}, branches with dashed lines
are terminal, the others are internal. The branching structure of
the tree trunk can be fully translated into a set of productions
$\mathscr{P}$. All productions in $\mathscr{P}$ are sorted in the
specified order, first bottom-up, then left-right. For the
convenience of expression, the production in $\mathscr{P}$ whose
predecessor equals to $p$ is denoted as $\mathscr{P}(p)$, the $i$th
production in $\mathscr{P}$ as $\mathscr{P}[i]$, the predecessor and successor of
a production $\mathscr{P}[i]$ as $\mathscr{P}[i].p$ and $\mathscr{P}[i].s$, and the $i$th ID in a successor $s$ as
$s[i]$.

In addition, we define \textbf{equivalent} productions as ones with
the same successors. Equivalent productions follow a property: if two productions $\mathscr{P}[i]$ and $\mathscr{P}[j]$
are equivalent, $\mathscr{P}[j].p$ appearing in the successor of a
production can be replaced by $\mathscr{P}[i].p$. In this case,
$\mathscr{P}[j]$ can be deleted from $\mathscr{P}$ for
simplification. This deletion can be repeated until there are no
equivalent productions in $\mathscr{P}$. The process of deletion is
called pre-reduction. An example is presented in
Table~\ref{tbl:reduction}, where the pre-reduction works on the
production set of the branching structure in Figure
\ref{fig:skeleton}.

However, the production set $\mathscr{P}$ after pre-reduction is
still unable to forecast the future structure of the tree trunk
because the process of rewriting new structures always stops at terminal branches.
To produce new branches, terminal branches have to be replaced with
internal branches. Besides, the set $\mathscr{P}$ includes many redundant
productions. To simplify productions, internal branches having the
similar successor need to be induced. This paper
proposes a \textbf{reduction} method to complete both tasks
mentioned above. Reduction is actually an iterative process of
reducing productions, and complies with the below statements:
\begin{dfn}
\label{dfn:terminalreduction}
If $b_1$ is a terminal branch, $b_1$ can be \textbf{reduced} by any branch.
\end{dfn}
\begin{dfn}
\label{dfn:nonterminalreduction} For internal branches $b_1$ and
$b_2$, if $\mathscr{P}(b_1).s$ has the same length as
$\mathscr{P}(b_2).s$, and $\mathscr{P}(b_1).s[i]$ can be
\textbf{reduced} by $\mathscr{P}(b_2).s[i]$ where $i = 0, 1 \cdots$,
$b_1$ can be \textbf{reduced} by $b_2$.
\end{dfn}

A reduction table $\mathscr{R}$ is needed during reduction. It lists
branches that are capable to replace others. Moreover, branches in a row of the
reduction table cannot replace each other.
Algorithm~\ref{alg:addtoreductiontable} $ART$ (abbr. for
``Add to Reduction Table'') in detail states the process of finding the
reduction relation and adding branches to $\mathscr{R}$.

%$\mathscr{R}(b)$ means the list in the second column of the table
%where the value of first column is $b$ and $\mathscr{R}(b)[i]$ means
%the $i$th branch in $\mathscr{R}(b)$.

\begin{algorithm}
\caption{ART} \label{alg:addtoreductiontable}

\SetKwInOut{Input}{input}
\SetKwInOut{Output}{output}

\Input{$b_1$ and $b_2$ (two internal branches), $\mathscr{R}$ (a reduction table)}

\BlankLine
\If{$b_1$ equals to $b_2$}{
    \Return;
}
\If{$b_2$ can be reduced by $b_1$}{
    exchange the values of $b_1$ and $b_2$;
}
\If{$b_1$ can be reduced by $b_2$}{
    $list \leftarrow \mathscr{R}(b_1)$;\\
    $reduced \leftarrow false$;\\
    \ForEach{$list[i]$}{
        \If{$list[i]$ can be reduced by $b_2$}{
            \textbf{ART}($list[i]$, $b_2$, $\mathscr{R}$);
            \Return;
        }
        \ElseIf{$b_2$ can be reduced by $list[i]$}{
            \textbf{ART}($b_2$, $list[i]$, $\mathscr{R}$);\\
            $list[i] \leftarrow b_2$;\\
            $reduced \leftarrow true$;
        }
    }
    \If{$reduced$ equals to $false$}{
        add $b_2$ to $list$;
    }
    $\mathscr{R}(b_1) \leftarrow list$;
}
\end{algorithm}

\newtheorem{crl}{Corollary}
\begin{crl}
\label{crl:reductionrelationship} If $b_1$ and $b_2$ \textbf{cannot} be
reduced by each other, and $b_1$ \textbf{can} be reduced by $b_3$, $b_2$ \textbf{cannot} be
reduced by $b_3$.
\end{crl}

The validity of the first $if$ in the $foreach$ block in
Algorithm~\ref{alg:addtoreductiontable} is ensured by
Corollary~\ref{crl:reductionrelationship}. There will not be any
other branch in $list$ that can be reduced by $b_2$ if $list[i]$
can be reduced by $b_2$. So there is a $return$ after the recursive
calling of $ART(list[i], b_2, \mathscr{R})$.
For a structure in the lower level of a tree, this algorithm can
find its similar structure in the higher level. For instance, branch $6$ in Figure~\ref{fig:branchingstructure} is considered by this algorithm as being similar to branch $13$.

A terminal branch can be reduced by a similar internal branch in our
algorithm. However, if a terminal branch does not have the similar
structure in the lower level, it can be reduced by the root
branch $r$.
\begin{table}[h]
\begin{center}
\begin{tabular}{|c|l|l|}
\hline
\multicolumn{1}{|c|}{$\textbf{ID}$} & \multicolumn{1}{|c|}{$\mathscr{P}(\textbf{ID}).s$} & \multicolumn{1}{|c|}{$\mathscr{R}(\textbf{ID})$}\\
\hline\hline
$r$ & $\{1, 2\}$ & $\{\}$\\
$1$ & $\{3, 14\}$ & $\{\}$\\
$2$ & $\{5, 6, 14\}$ & $\{\}$\\
$3$ & $\{14, 13\}$ & $\{r\}$\\
$5$ & $\{14, 14\}$ & $\{1\}$\\
$6$ & $\{14, 13, 14\}$ & $\{2\}$\\
$13$ & $\{t, t, t\}$ & $\{6\}$\\
$14$ & $\{t, t\}$ & $\{3, 5\}$\\
\hline
\end{tabular}
\end{center}
\caption{$\mathscr{P}$ and $\mathscr{R}$ after pre-reduction.}
\label{tbl:reduction}
\end{table}

The final reduction table $\mathscr{R}$ will be used to reduce
$\mathscr{P}$. The reduction process is presented in
Algorithm~\ref{alg:reduce}.
\begin{algorithm}
\caption{Reduction} \label{alg:reduce} \SetKwInOut{Input}{input}
\SetKwInOut{Output}{output}
\Input{$\mathscr{P}$ (production set), $\mathscr{R}$ (reduction table), $r$ (the ID of the root branch)}
\BlankLine
$n \leftarrow$ size of $\mathscr{P}$;\\
\For{$i = n - 1$ \emph{\KwTo} $0$}{
    $list \leftarrow \mathscr{R}(\mathscr{P}[i].p)$;\\
    find the branch $b$ in $list$ who has the lowest level in the tree;\\
    replace all $\mathscr{P}[i].p$ in the successor of any production with branch $b$;
}
replace the rest terminal branches with $r$;
\end{algorithm}
A result of Algorithm~\ref{alg:reduce} is that no terminal
branches appear in the successor of any production in $\mathscr{P}$.
In addition, since some productions lose the connectivity to the root branch, they are deleted from $\mathscr{P}$.
The final axiom $r$ and
the production set $\mathscr{P}$ can be extracted after running
Algorithm~\ref{alg:reduce}. Table~\ref{tbl:lsystem} shows the
extracted axiom and productions of the branching structure in
Figure~\ref{fig:skeleton}.
\begin{table}[h]
\begin{center}
\begin{tabular}{|c|l|}
\hline
$\textbf{Axiom}$ & \multicolumn{1}{|c|}{$\mathscr{P}$}\\
\hline\hline
& $r \rightarrow \{1, 2\}$;\\
{$r$} & $1 \rightarrow \{r, r\}$;\\
& $2 \rightarrow \{1, 2, r\};$\\
\hline
\end{tabular}
\end{center}
\caption{The extracted axiom and productions of Figure~\ref{fig:skeleton}.}
\label{tbl:lsystem}
\end{table}

\subsection{Parameter extraction}
\label{sec:lsystemextraction:parameter}

To better control the shape of the tree trunk, a set of parameters should be introduced to extend the original L-system to a parametric version. These parameters are:

\begin{enumerate}
\item \textbf{Length of branch:} The Euclidean distance between the starting point and the terminal point;
\item \textbf{Width of branch:} The value in the distance map obtained in Section~\ref{sec:Pre-processing};
\item \textbf{Branching angle:} The angle between the parent and child branches, as illustrated by $\alpha$ in Figure~\ref{fig:angles};
\item \textbf{Divergence angle:} The angle describing the child's diverging degree from the plane spanned by its parent and grandparent, as illustrated by $\beta$ in Figure~\ref{fig:angles}.
\end{enumerate}

Each parameter is extracted for every branch in the 3D skeleton. It is recorded in an ordered list so that it can be located in the right position during the L-system parsing process.

\begin{figure}
\centering

\begin{tikzpicture}[path fading=south]

%help line
%\draw[help lines, gray] (0,0,0) grid (5,5,5);

%rectangle bkg
\path[fill=gray, semitransparent, path fading=north]
(-1.5,0,-2) -- (3,0,-2) -- (3,0,3) -- (-1.5,0,3);
\node[gray, above] at (-1.5,0,3) {$P$};

%branches
\draw[red, ->] (0,0,0) to node[left] {$\vec{g}$} (0,1.732,0);
\draw[green, ->] (0,1.732,0) to node[anchor=south east] {$\vec{p}$} (1,2.732,1);
\draw[purple, ->] (1,2.732,1) to node[below] {$\vec{c}$} (2.6583,3.232,1);
\draw[purple, ->] (1,2.732,1) to (1,4.146,0);
\draw[green, ->] (0,1.732,0) to (-1,3.146,0);

%vlines
\draw[loosely dashed, green] (1,2.732,1) to (1,0,1);
\draw[loosely dashed, purple] (2.6583,3.232,1) to (2.6583,0,1);

%projective branches
\draw[densely dashed, green, ->] (0,0,0) to node[anchor=north east] {$\vec{q}$} (1,0,1);
\draw[densely dashed, purple, ->] (1,0,1) to node[above] {$\vec{d}$} (2.6583,0,1);

%extented lines
\draw[green, densely dashed] (1,2.732,1) to (2.5,4.232,2.5);
\draw[green, densely dashed] (1,0,1) to (2.5,0,2.5);

%arcs
\draw[blue, densely dashed] (1.4787,2.8763,1) arc (10.6523:39.5:0.5);
\node[blue] at (1.732,3.15,1) {$\alpha$};
\draw[blue, densely dashed] (1.5,0,1) arc (0:-40:0.5);
\node[blue] at (1.732,-0.21,1) {$\beta$};

\end{tikzpicture}
\caption{Branch $g$ is the parent of branch $p$ who has a child branch $c$. Branching angle $\alpha$ of branch $c$ is the angle hold by vector $\vec{p}$ and $\vec{c}$. $P$ is a plane whose normal is vector $\vec{g}$. $\vec{q}$ and $\vec{d}$ are projections of $\vec{p}$ and $\vec{c}$ on $P$. Divergence angle $\beta$ of branch $c$ is the angle hold by $\vec{q}$ and $\vec{d}$.}
\label{fig:angles} %% label for entire figure
\end{figure}

%-------------------------------------------------------------------------
\subsection{Parameter completion}

The extracted L-system comes from visible trunk of the tree.
It need to be complemented to cover the occluded trunk and the leaves.
The completion is mainly to conclude the parameters
under the instruction of the extracted L-system
and the constraint of silhouettes in the images.

The silhouettes in both images are extracted using
the same method as extracting the visible trunk
in Section~\ref{sec:Pre-processing}.
Our approach let the existing L-system continue to grow
to generate occluded trunk.
The new-grown branches need parameters introduced
in Section~\ref{sec:lsystemextraction:parameter}
to determine their positions.
We use a specified value for the \textbf{length of branch}.
This value is small in order to make the occluded trunk
fill the silhouette sufficiently.
The \textbf{width of branch} is determined by the width
of its parent and the global decrement calculated from
the visible branches.
Then two fitting curves are made on \textbf{branching angle}
and \textbf{divergence angle}.
According to our experiments, these two angles present
periodicity, therefore the Fourier fitting method is chosen.
Branching angles and divergence angles of occluded branches
are determined by these two curves.
Once a new branch is generated, it is checked if it falls
in both silhouettes in the two source images.
Since the branches are generated in 3D space,
it is projected to the two image planes using
the projective matrix~\cite{Hartley00} before checking.
If the new branch falls in the silhouettes
and does not hit it, it continues growing.
If the terminal point of the new branch
is near the silhouette, it stops growing.
If the fall-in rate is smaller than a threshold,
cut it at the intersection to the silhouette.
Figure~\ref{fig:insert} illustrates the growth
of the occluded branches.
During the growth of the occluded branches,
all parameter values are preserved after
the ones of the visible branches.

All leaves share one surface that is predefined.
This surface has a scale factor to adjust
the size of the leaf.
This scale factor is calculated by the mean distance
from the occluded branch to the nearest silhouette point.

\begin{figure}
  \centering
  \subfigure[]{
    \label{fig:insert:a} %% label for first subfigure
    \includegraphics[scale=0.3]{Figure/insert_source.jpg}
    }
  \hfill
  \subfigure[]{
    \label{fig:insert:b} %% label for first subfigure
    \includegraphics[scale=0.3]{Figure/insert_before.jpg}
    }
  \hfill
  \subfigure[]{
    \label{fig:insert:c} %% label for first subfigure
    \includegraphics[scale=0.3]{Figure/insert_after.jpg}
    }
  \caption{(a) Source image, the red line is a visible branch and the blue line is the silhouette;
  (b) Before cutting, the orange branches need to be cut; (c) After cutting.}
  \label{fig:insert} %% label for entire figure
\end{figure}

%-------------------------------------------------------------------------
\section{Model usage}

The extracted L-system is a parametric tree model.
It can be easily transformed to a mesh model for rendering.
The geometry interpretation for L-system is in~\cite{Lindenmayer68}.
An strong L-system modeling tool L-studio 
is also developed in~\cite{PRUSINKIEWICZ99} for L-system study.
\httpAddr {//algorithmicbotany.org} lists many usage
of L-system.
Moreover, since L-system is a light-weighted model
(usually a text file with a few small textures and other stuffs),
it is preferable to transfer on Web.
The interpretation can be executed at the client machine
before rendering.
It may bring great benefit for Web virtual reality applications,
esp. virtual tour, virtual natural landscape
and virtual agriculture.

%-------------------------------------------------------------------------
\section{Experiment results}

Please follow the steps outlined in this document very carefully when
submitting your manuscript to Eurographics.

You may as well use the \LaTeX\ source as a template to typeset your own
paper. In this case we encourage you to also read the \LaTeX\ comments
embedded in the document.

%-------------------------------------------------------------------------
\section{Conclusions}

Please follow the steps outlined in this document very carefully when
submitting your manuscript to Eurographics.

You may as well use the \LaTeX\ source as a template to typeset your own
paper. In this case we encourage you to also read the \LaTeX\ comments
embedded in the document.

%-------------------------------------------------------------------------
\section{Introduction}

Please follow the steps outlined in this document very carefully when
submitting your manuscript to Eurographics.

You may as well use the \LaTeX\ source as a template to typeset your own
paper. In this case we encourage you to also read the \LaTeX\ comments
embedded in the document.

%-------------------------------------------------------------------------
\section{Instructions}

Please read the following carefully.

%-------------------------------------------------------------------------
\subsection{Language}

All manuscripts must be in English.

%-------------------------------------------------------------------------
\subsection{Margins and page numbering}

All printed material, including text, illustrations, and charts,
must be kept within a print area 6.31 inches (16.03 cm) wide by
9.10 inches (23.13 cm) high. Do not write or print anything
outside the print area. Number your pages on odd sites right
above, on even sites left above, no page number on the first site.
Do not use page numbering within the final version of your paper.


%------------------------------------------------------------------------
\subsection{Formatting your paper}

All text with the exception of the abstract must be in a two-column format.
The total allowable width of the text area -- including header and footer
lines -- is 161\,mm (6.34 inch) wide by 231\,mm (9.10 inch) high.

Columns are to be 76\,mm (3.0 inch) wide, with a 8\,mm (0.315 inch) space
between them.

The space between the header line and the first line of the text body and
between the last line of the text body and the footer line is 5\,mm
(0.196 inch) each.

%-------------------------------------------------------------------------
\subsection{Type-style and fonts}

Wherever Times is specified, Times Roman may also be used. If
neither is available on your word processor, please use the font
closest in appearance to Times that you have access to. Only
Type-1 fonts will be accepted.

MAIN TITLE. The title should be in Times 17-point, boldface type and
centered. Capitalize the first letter of nouns, pronouns, verbs, adjectives,
and adverbs; do not capitalize articles, coordinate conjunctions, or
prepositions (unless the title begins with such a word). Leave two blank
lines after the title.

AUTHOR NAME(s) and AFFILIATION(s) are to be centered beneath the title and
printed in Times 9-point, non-boldface type. This information is to be
followed by two blank lines.

The ABSTRACT ist to be in a one-column format. The MAIN TEXT is to be in a
two-column format.

MAIN TEXT. Type main text in 9-point Times, single-spaced. Do \emph{not} use
double-spacing. All paragraphs should be indented 1 em (the length of the
dash in the actual font). Make sure your text is fully justified -- that is,
flush left and flush right. Please do not place any additional blank lines
between paragraphs. Figure and table captions should be 9-point Times
boldface type as in Figure~\ref{fig:firstExample}.

\noindent Long captions should be set as in Figure~\ref{fig:ex1} or
Figure~\ref{fig:ex3}.

\begin{figure}[htb]
   % an empty figure just consisting of the caption lines
   \caption{\label{fig:ex1}
     'Empty' figure only to serve as an example of long caption requiring
     more than one line. It is not typed centered but aligned on both sides.}
\end{figure}

\noindent
Figures which need the full textwidth can be typeset as Figure~\ref{fig:ex3}.

\noindent Callouts should be 9-point Times, non-boldface type. Initially
capitalize only the first word of section titles and first-, second-, and
third-order headings.

FIRST-ORDER HEADINGS. (For example, \textbf{1. Introduction}) should be Times
9-point boldface, initially capitalized, flush left, with one blank line
before, and one blank line after.

SECOND-ORDER HEADINGS. (For example, \textbf{2.1. Language}) should be Times
9-point boldface, initially capitalized, flush left, with one blank line
before, and one after. If you require a third-order heading (we discourage
it), use 9-point Times, boldface, initially capitalized, flush left, preceded
by one blank line, followed by a period and your text on the same line.

The headline \emph{(authors / title)} must be shortened if it uses the full
two column width of the main text.
There must be enough space for the page numbers. Please use ``et al.'' if
there are more than three authors and specify a shortened version for your title.
%-------------------------------------------------------------------------
\subsection{Footnotes}

Please do \emph{not} use footnotes at all!


%-------------------------------------------------------------------------
\subsection{References}

List all bibliographical references in 9-point Times, single-spaced, at the
end of your paper in alphabetical order. When referenced in the text, enclose
the citation index in square brackets, for example~\cite{Lous90}. Where
appropriate, include the name(s) of editors of referenced books.

For your references please use the following algorithm:
\begin{itemize}
\item \textbf{one} author: first 3 chars plus year --
      e.g.\ \cite{Lous90}
\item \textbf{two}, \textbf{three} or \textbf{four} authors: first char
      of each family name plus year --  e.g.\ \cite{Fellner-Helmberg93}
      or \cite{Kobbelt97-USHDR} or \cite{Lafortune97-NARF}
\item \textbf{more than 4} authors: first char of family name from
      first 3 authors followed by a '*' followed by the year --
      e.g.\ \cite{Buhmann:1998:DCQ} or \cite{FolDamFeiHug.etal93}
\end{itemize}

For BibTeX users a style file \ \texttt{eg-alpha.bst} \ is available which
uses the above algorithm.

%-------------------------------------------------------------------------
\subsection{Illustrations, graphs, and photographs}

All graphics should be centered.

%%%
%%% Figure 1
%%%
\begin{figure}[htb]
  \centering
  % the following command controls the width of the embedded PS file
  % (relative to the width of the current column)
  \includegraphics[width=.8\linewidth]{sampleFig}
  % replacing the above command with the one below will explicitly set
  % the bounding box of the PS figure to the rectangle (xl,yl),(xh,yh).
  % It will also prevent LaTeX from reading the PS file to determine
  % the bounding box (i.e., it will speed up the compilation process)
  % \includegraphics[width=.95\linewidth, bb=39 696 126 756]{sampleFig}
  %
  \parbox[t]{.9\columnwidth}{\relax
           For all figures please keep in mind that you \textbf{must not}
           use images with transparent background!
           }
  %
  \caption{\label{fig:firstExample}
           Here is a sample figure.}
\end{figure}

If your paper includes images, it is very important that they are of
sufficient resolution to be faithfully reproduced.

To determine the optimum size (width and height) of an image, measure
the image's size as it appears in your document (in millimeters), and
then multiply those two values by 12. The resulting values are the
optimum $x$ and $y$ resolution, in pixels, of the image. Image quality
will suffer if these guidelines are not followed.

Example 1:
%
An image measures 50\,mm by 75\,mm when placed in a document. This
image should have a resolution of no less than 600 pixels by 900
pixels in order to be reproduced faithfully.

Example 2:
%
Capturing a screenshot of your entire $1024 \times 768$ pixel display
monitor may be useful in illustrating a concept from your research. In
order to be reproduced faithfully, that $1024 \times 768$ image should
be no larger than 85 mm by 64 mm (approximately) when placed in your
document.


%-------------------------------------------------------------------------
\subsection{Color}

\textbf{Please observe:} as of 2003 publications in the proceedings of the
Eurographics Conference can use color images throughout the paper. No
separate color tables are necessary.

However, workshop proceedings might have different agreements!
Figure~\ref{fig:ex3} is an example for creating color plates.

%------------------------------------------------------------------------
\subsection{Embedding of Hyperlinks / Typesetting of URLs}

Due to the use of the package \texttt{hyperref} the original behavior
of the command $\backslash$\texttt{url} from the package \texttt{url}
is not available. To circumvent this problem we either recommend to
use the command $\backslash$\texttt{httpAddr} from the
included package \texttt{egweblnk} (see below) or to replace the
command $\backslash$\texttt{url} by the command $\backslash$\texttt{webLink}
-- e.g. in cases where $\backslash$\texttt{url} has been used
widely in BibTeX-References. In the latter case we suggest to run
BibTeX as usual and then replace all occurences of $\backslash$\texttt{url}  by
$\backslash$\texttt{webLink}

\noindent
The provided commands for hyperlinks, in a nutshell, are:

\begin{description} \itemsep 1ex
\item [\webLinkFont $\backslash$httpAddr \{URL without leading 'http:'\}]
      \mbox{}\\
      e.g. \  \httpAddr{//diglib.eg.org/EG/DL/WS}

\item[\webLinkFont $\backslash$ftpAddr \{URL without leading 'ftp:'\}]
      \mbox{}\\
      e.g. \  \ftpAddr{//www.eg.org/EG/DL/ftpupload}

\item[\webLinkFont $\backslash$URL \{url\}]
      \mbox{}\\
      e.g. \  \URL{http://www.eg.org/EG/DL/WS}

\item[\webLinkFont $\backslash$MailTo \{Email addr\}]
      \mbox{}\\
      e.g. \  \MailTo{publishing@eg.org}

\item[\webLinkFont $\backslash$MailToNA \{emailName\}\{@emailSiteAddress\}]
      \mbox{}\\
      e.g. \  \MailToNA{publishing}{@eg.org}

\item[\webLinkFont $\backslash$webLink\{URL without hyperlink creation\}]
      \mbox{}\\
      e.g. \  \webLink{http://www.eg.org/some_arbitrary_long/but_useless/URL}

\end{description}


%------------------------------------------------------------------------
\subsection{PDF Generation}

Your final paper should be delivered as a PDF document with all typefaces
embedded. \LaTeX{} users should use \texttt{dvips} and \texttt{ps2pdf} to
create this PDF document. Adobe Acrobat Distiller may be used in place of
\texttt{ps2pdf}.

Adobe PDFWriter is \emph{not} acceptable for use. Documents created with
PDFWriter will be returned to the author for revision. \texttt{pdftex} and
\texttt{pdflatex} (and its variants) can be used only if the author can
make certain that all typefaces are embedded and images are not downsampled
or subsampled during the PDF creation process.

Users with no access to these PDF creation tools should make available a
PostScript file and we will make a PDF document from it.


The PDF file \emph{must not} be change protected.

%------------------------------------------------------------------------
\subsubsection*{Configuration Notes: dvips / ps2pdf / etc.}

\noindent
\texttt{dvips} should be invoked with the \texttt{-Ppdf} and \texttt{-G0}
flags in order to use Type 1 PostScript typefaces:

\begin{verbatim}
    dvips -t a4 -Ppdf -G0 -o my.ps my.dvi
\end{verbatim}


\noindent
If you are using version 7.x of GhostScript, please use the following method of invoking \texttt{ps2pdf}, in
order to embed all typefaces and ensure that images are not downsampled or subsampled in the PDF
creation process:

\begin{verbatim}
  ps2pdf -dMaxSubsetPct=100 \
         -dCompatibilityLevel=1.3 \
         -dSubsetFonts=true \
         -dEmbedAllFonts=true \
         -dAutoFilterColorImages=false \
         -dAutoFilterGrayImages=false \
         -dColorImageFilter=/FlateEncode \
         -dGrayImageFilter=/FlateEncode \
         -dMonoImageFilter=/FlateEncode \
         mypaper.ps mypaper.pdf
\end{verbatim}


If you are using version 8.x of GhostScript, please use this method in place of the example above:
\begin{verbatim}
  ps2pdf -dPDFSETTINGS=/prepress \
         -dCompatibilityLevel=1.3 \
         -dAutoFilterColorImages=false \
         -dAutoFilterGrayImages=false \
         -dColorImageFilter=/FlateEncode \
         -dGrayImageFilter=/FlateEncode \
         -dMonoImageFilter=/FlateEncode \
         -dDownsampleColorImages=false \
         -dDownsampleGrayImages=false \
         mypaper.ps mypaper.pdf
\end{verbatim}

%------------------------------------------------------------------------
\subsubsection*{Configuration Notes: pdftex / pdflatex / etc.}

\noindent
Configuration of these tools to embed all typefaces can be accomplished by editing the \texttt{updmap.cfg} file
to enable inclusion of the standard (or base) 14 typefaces.

Linux users can run the \texttt{updmap} script to do this:
\begin{verbatim}
updmap --setoption pdftexDownloadBase14 true
\end{verbatim}

Windows users should edit the \texttt{updmap.cfg} files found in their TeX installation directories (one or both
of the following may be present):
\begin{verbatim}
  INSTALLDIR\texmf\web2c\updmap.cfg
  INSTALLDIR\localtexmf\miktex\config\updmap.cfg
\end{verbatim}

Ensure the value for \texttt{pdftexDownloadBase14} is "true," and then follow the instructions found here:
\httpAddr{//docs.miktex.org/manual/} to update your MikTeX installation.

%------------------------------------------------------------------------
\subsubsection*{Configuration Notes: Acrobat Distiller}

We recommend to download and install the version of the ``CMW'' Adobe Acrobat Distiller job options file
appropriate for your operating system and version of Acrobat from the following URL:

\httpAddr{//www.cadmusmediaworks.com/index2.html}\\
in the ``(Operating System)/Applications/Distiller Settings'' folder. The ``CMW'' job options file embeds
all typefaces and does not downsample or subsample images when creating the PDF document.
%------------------------------------------------------------------------
\subsection{Copyright forms}

You must include your signed Eurographics copyright release form
when you submit your finished paper. We MUST have this form before
your paper can be published in the proceedings.

%-------------------------------------------------------------------------
\subsection{Conclusions}

Please direct any questions to the production editor in charge of
these proceedings.

%-------------------------------------------------------------------------

\bibliographystyle{eg-alpha}

\bibliography{egbibsample}

%-------------------------------------------------------------------------
\newpage


\begin{figure*}[tcb]
  \centering
  \mbox{} \hfill
  % the following command controls the width of the embedded PS file
  % (relative to the width of the current column)
  \includegraphics[width=.3\linewidth]{sampleFig}
  % replacing the above command with the one below will explicitly set
  % the bounding box of the PS figure to the rectangle (xl,yl),(xh,yh).
  % It will also prevent LaTeX from reading the PS file to determine
  % the bounding box (i.e., it will speed up the compilation process)
  % \includegraphics[width=.3\linewidth, bb=39 696 126 756]{sampleFig}
  \hfill
  \includegraphics[width=.3\linewidth]{sampleFig}
  \hfill \mbox{}
  \caption{\label{fig:ex3}%
           For publications with color tables (i.e., publications not offering
           color throughout the paper) please \textbf{observe}:
           for the printed version -- and ONLY for the printed
           version -- color figures have to be placed in the last page.
           \newline
           For the electronic version, which will be converted to PDF before
           making it available electronically, the color images should be
           embedded within the document. Optionally, other multimedia
           material may be attached to the electronic version. }
\end{figure*}

\end{document}
